1. Field of Use
This present invention relates to data processing systems having a memory hierarchy which includes a high speed buffer store or cache unit.
2. Prior Art
It is well known that many data processing systems each include a main memory or main store and high speed low capacity buffer store or cache, each of which is positioned between the system's data processing unit and its main memory. In such systems, an associative memory normally is used to store the block addresses for indicating which blocks are stored or reside in the cache or buffer store. When a fetch or read request occurs, the associative memory is interrogated to determine whether the block containing the addressed word resides in cache. If not, the word together with associated words of a block are fetched from main store and read into cache or buffer store.
Generally recognized are the cost advantages of having the cache or buffer store contain a limited number of blocks to minimize the size of associative memory. However, others have recognized certain disadvantages resulting from such storage limitations in the case of block transfers. In overcoming such disadvantages, one high speed memory system provides a high degree of overlap or concurrency wherein additional accesses to the memory system may be executed after a block transfer has been initiated. U.S. Pat. No. 3,588,829 is an example of one such system.
In providing such overlap, it is possible to receive more than one request specifying fetching data from the same block. To avoid the generation of multiple commands to main memory or backing store, additional comparison circuits or associative memory circuits together with a multiplicity of control bits are included to detect conflicting requests with respect to certain types of commands. Also, the arrangement includes control sequencing circuits which are also responsive to certain control bits to establish the manner in which commands are to be sequenced. During additional cycles, comparisons are made and the results are stored to be used to control the fetching of commands. Such arrangements have found to result in increased cost and complexity. Moreover, such arrangements are unable to process a variety of different types of commands which give rise to increases of overlap. Also, the setting and resetting of various control bits for command sequencing involving establishing necessary priorities have been found to be time consuming.
Another prior art cache unit included a control directory including a plurality of multibit locations corresponding in number to the number of blocks. One of the bit locations identified by a memory command was set to a predetermined state. This occured when the command called for an operation which could not be completed immediately but which remained outstanding for a certain minimum length of time.
During the processing of subsequently received commands, the contents of the control directory are accessed. When a next memory command is received which specifies information requested by previous commands and the contents of control directory bit location indicate whether the operation which has been initiated is still pending or outstanding. When the contents indicate that the operation is outstanding, the control circuits signal the processor to stop its operation in the case where the information requested is needed immediately. When all of the information required to complete the pending operation has been stored in the cache unit, the control sequencing circuits automatically reexecute such next command and enable processor to continue operation.
By referencing the contents of the control directory during the normal command processing, the system is able to detect the presence of conflicting commands and prevent the issuance of duplicate commands.
For further information regarding this arrangement, reference may be made to the copending patent application "Buffer Store Including Control Apparatus Which Facilitates the Concurrent Processing of a Plurality of Commands", invented by Charles P. Ryan, bearing Ser. No. 853,982, filed on Nov. 22, 1977.
In the above prior art arrangement, processor operation was stopped or held up in the case of conflicting read commands. However, with respect to write commands, the processing of such write commands was held up until the execution of all outstanding read commands had been completed. While the arrangement prevented the issuance of duplicate commands, the processing of certain types of commands, such as write commands, was delayed. This could result in decreased processing efficiency.
Accordingly, it is a primary object of the present invention to provide a buffer store or cache arrangement which permits a high degree of overlap with minimal increases in cost and complexity.
It is a further object of the present invention to provide a low cost buffer store or cache capable of executing all types of memory commands without requiring the issuance of duplicate commands with minimum delay in processing.